package a2_p04_jw_kw.searchalgo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.DirectedPseudograph;

import a1_p04_jw_kw.graph.GraphUtility;
import a1_p04_jw_kw.struct.Node;

public class Dijkstra {
	private static double INFINITE = 99999999.0;

	HashMap<Node, Double> distances = new HashMap<Node, Double>();// formally known as entfI/entfL
	HashMap<Node, Node> parentList = new HashMap<Node, Node>();// formally known as vorgI
	HashMap<Node, Boolean> okList = new HashMap<Node, Boolean>();
	
	int count = 0;

	Graph<Node, DefaultWeightedEdge> g;
	Node start;

	public Dijkstra(Graph<Node, DefaultWeightedEdge> g,
			String start) {
		this.g = g;
		this.start = GraphUtility.getNode(g, start);

		this.initialize();
		this.start();
	}
	
	public Dijkstra(Graph<Node, DefaultWeightedEdge> g) {
		
		this.g = g;
		this.start = getStartNodeByAttribute();
		
		this.initialize();
		this.start();
		
	}

	// initialize the dijkstra
	private void initialize() {
		for (Node n : this.g.vertexSet()) {
			this.distances.put(n, (Double) INFINITE);
			this.parentList.put(n, null);
			this.okList.put(n, false);

			// set values to the starting vertex
			if (n.equals(this.start)) {
				this.distances.put(n, 0.0);
				this.parentList.put(n, n);
			}
		}

	}

	private void start() {
		while (hasUnexaminedVertices()) {
			count ++;
			
			// getNextVertex
			Node currentVertex = getNextVertexToExamine();
			// set vertex as examined
			okList.put(currentVertex, true);

			// for all unexamined successors
			for (Node n : getUnexaminedSuccesors(currentVertex)) {
				// if current length to the unexaminedSuccessor is higher then
				// the length of the current vertex + the weight of the edge to
				// the unexaminedSuccesor, set a new length 
				double lengthToUnexaminedSuccessor = distances.get(currentVertex) + g
						.getEdgeWeight(g.getEdge(currentVertex, n));
				
				if (distances.get(n) > lengthToUnexaminedSuccessor) {
					
					distances.put(n,((Double)lengthToUnexaminedSuccessor));
					parentList.put(n, currentVertex);

				}
			}

		}

	}

	// gets the node from entfI with the lowest value
	private Node getNextVertexToExamine() {
		Node vertexWithLowestValue = null;
		double lowestValue = -1.0;

		for (Map.Entry<Node, Double> entry : this.distances.entrySet()) {
			// if their is currently no vertex with a lowest value, get the
			// first from the map
			if ((vertexWithLowestValue == null) && !isExamined(entry.getKey())) {
				vertexWithLowestValue = entry.getKey();
				lowestValue = entry.getValue();
			}

			// if the current entry.value is lower than the one stalled in
			// lowestValue set new vertexWithLowestValue
			if ((entry.getValue() < lowestValue) && !isExamined(entry.getKey())) {
				vertexWithLowestValue = entry.getKey();
				lowestValue = entry.getValue();

			}

		}

		return vertexWithLowestValue;
	}

	private boolean isExamined(Node node) {
		if (okList.get(node)) {
			return true;

		}

		return false;
	}

	private boolean hasUnexaminedVertices() {
		for (Map.Entry<Node, Boolean> entry : this.okList.entrySet()) {
			if (!entry.getValue()) {
				return true;

			}
		}

		return false;
	}

	// return all unexamined successors
	private ArrayList<Node> getUnexaminedSuccesors(Node node) {
		ArrayList<Node> unexaminedSuccesors = new ArrayList<Node>();

		// get all successors and check if they are already examined
		for (Node n : Graphs.neighborListOf(this.g, node)) {
			if (!isExamined(n)) {
				unexaminedSuccesors.add(n);
				
			}

		}

		return unexaminedSuccesors;
	}
	
	public double getLenghtToTarget(String target) {
		return distances.get(GraphUtility.getNode(this.g, target));
		
	}
	
	public ArrayList<Node> getBestWayToTarget(String target) {
		Node n = GraphUtility.getNode(this.g, target);
		ArrayList<Node> bestWay = new ArrayList<Node>();
		
		bestWay.add(n);
		
		while (!n.equals(this.start)) {
			Node predeccessor = parentList.get(n);
			bestWay.add(predeccessor);
			n = predeccessor;
			
		}
		
		return bestWay;
	}
	
	public int getCount() {
		return count;
		
	}

	private Node getStartNodeByAttribute() {
		for (Node n : this.g.vertexSet()) {
			if (n.isStart) {
				return n;
				
			}
		}
		
		return null;
	}
}
